package com.lfg.leetcode.leetcode300;


import java.util.ArrayList;
import java.util.List;

public class No352SummaryRanges {
    public static void main(String[] args) {
        SummaryRanges obj = new SummaryRanges();
        int[] nums = new int[]{
                49, 97, 53, 5, 33, 65, 62, 51, 100, 38, 61, 45, 74, 27, 64, 17, 36, 17, 96, 12, 79, 32, 68, 90, 77, 18, 39, 12,
                93, 9, 87, 42, 60, 71, 12, 45, 55, 40, 78, 81, 26, 70, 61, 56, 66, 33, 7, 70, 1, 11, 92, 51, 90, 100, 85, 80, 0,
                78, 63, 42, 31, 93, 41, 90, 8, 24, 72, 28, 30, 18, 69, 57, 11, 10, 40, 65, 62, 13,
                38, 70, 37, 90, 15, 70, 42, 69, 26, 77, 70, 75, 36, 56, 11, 76, 49, 40, 73, 30, 37, 23};
//        int[] nums = new int[]{1, 3, 7, 2, 6};
        for (int i : nums) {
            obj.addNum(i);
            System.out.println(obj.getIntervals());
        }
    }
}


class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }

    public String toString() {
        return start + "," + end;
    }
}

class SummaryRanges {
    List<Interval> list = null;

    public SummaryRanges() {
        list = new ArrayList<>(100);
    }

    public void addNum(int val) {
        if (list.isEmpty()) {
            list.add(new Interval(val, val));
            return;
        }
        int i = findIndex(val);
        int size = list.size();
        Interval interval = null;
        for (; i < size; i++) {
            interval = list.get(i);
            if (val >= interval.start && val <= interval.end) {
                return;
            } else if (val >= interval.start && val <= interval.end + 1) {
                interval.end = val;
                if (++i < size) {
                    Interval next = list.get(i);
                    if (next.start - interval.end <= 1) {
                        interval.end = next.end;
                        list.remove(i);
                    }
                }
                return;
            } else if (val == interval.start - 1) {
                interval.start = val;
                if (--i >= 0) {
                    Interval last = list.get(i);
                    if (interval.start - last.end <= 1) {
                        interval.start = last.start;
                        list.remove(i);
                    }
                }
                return;
            } else if (val < interval.start - 1) {
                list.add(i, new Interval(val, val));
                return;
            }
        }
        if (i >= size) {
            list.add(new Interval(val, val));
        }
    }

    public List<Interval> getIntervals() {
        return list;
    }

    public int findIndex(int val) {
        if (list.isEmpty()) {
            return 0;
        }
        int mid = 0;
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            mid = (start + end) / 2;
            Interval interval = list.get(mid);
            if (interval.start - 1 <= val && interval.end + 1 >= val) {
                break;
            } else if (interval.start - 1 > val) {
                end = mid - 1;
            } else if (interval.end + 1 < val) {
                start = mid + 1;
            }
        }
        if (mid > 0) {
            mid--;
        }
        return mid;
    }
}


